package cn.edu.zjut.algorithm;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author angzhijin
 * @Description 排序算法 - 冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数
 * BreakPoint 处打上断点可以调试查看各个子序列的排列情况
 * @create 2022-03-04 3:50 下午
 */
public class sortAlgorithm {
    private static int[] before = new int[]{4, 6, 2, 7, 16, 2, 72, 1, 7, 16, 8}; //随便选的数字
    private static int[] before2 = new int[]{99, 88, 77, 66, 55, 44, 33, 22, 11, 0}; //倒序转顺序

    private static int[] arr = new int[]{5, 7, 2, 4,3};

    public static void main(String[] args) {
        System.out.println("排序前：" + Arrays.toString(arr));
//        System.out.println("冒泡排序："+ Arrays.toString(bubbleSort(arr)));
//        System.out.println("选择排序："+ Arrays.toString(selectionSort(arr)));
//        System.out.println("插入排序："+ Arrays.toString(insertionSort(arr)));
//        System.out.println("希尔排序："+ Arrays.toString(shellSort(arr)));
//        System.out.println("归并排序："+ Arrays.toString(mergeSort(arr)));
//        System.out.println("快速排序："+ Arrays.toString(quickSort(arr)));
        System.out.println("堆排序：" + Arrays.toString(heapSort(arr)));
//        System.out.println("计数排序：" + Arrays.toString(countingSort(before)));
//        System.out.println("桶排序：" + Arrays.toString(bucketSort(before)));
//        System.out.println("基数排序：" + Arrays.toString(radixSort(before)));
    }

    /**
     * 冒泡排序 BubbleSort
     * 不断将最大值往后推
     *
     * 优化：添加flag，判断一次遍历中是否进行了交换，若没有，说明已经排序好（但对提升性能没太大作用）
     * 5 7 2 3 6
     * 5 2 7 3 6
     * 5 2 3 7 6
     * 5 2 3 6 7
     * 2 5 3 6 7
     * 2 3 5 6 7
     */
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { //BreakPoint
            boolean flag = true;
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = false;
                }
            }
            if (flag) break;
        }
        return arr;
    }

    /**
     * 选择排序 SelectionSort
     * 从头开始，找到较小值进行交换
     *
     * 优化：同样可以采用flag判断一轮中是否有交换来确定是否已完成
     *
     * 5 7 2 3 6
     * 2 7 5 3 6
     * 2 3 5 7 6
     * 2 3 5 6 7
     */
    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { //BreakPoint
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
        return arr;
    }

    /**
     * 插入排序 InsertionSort
     * 参考 扑克牌插牌
     *
     * 5 7 2 3 6
     * 2 5 7 3 6
     * 2 3 5 7 6
     * 2 3 5 6 7
     */
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { // i表示[0,i)都是有序的 //BreakPoint
            // i是要插的牌
            int tmp = arr[i];
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1]; // 大的往后移
                j--;
            }
            if (j != i)
                arr[j] = tmp; // 小的往前插
        }
        return arr;
    }

    /**
     * 希尔排序 ShellSort
     * 插入排序的优化
     * 基本思路：先跳着(step>1)进行插入排序，基本有序后整体(step=1)插入排序
     *
     * 5 7 2 3 4
     * 2 7 5 3 4
     * 2 3 5 7 4
     * 2 3 4 7 5
     * 2 3 4 5 7
     */
    public static int[] shellSort(int[] arr) {
        int length = arr.length;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) { //BreakPoint
                int tmp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = tmp;
            }
        }
        return arr;
    }

    /**
     * 归并排序 mergeSort
     *
     * 7 5 2 4 3
     * 7 5|2 4 3
     * 7|5|2|4 3
     * 5 7|2|4|3
     * 5 7|2|3 4
     * 5 7|2 3 4
     * 2 3 4 5 7
     */
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        int middle = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
        return merge(mergeSort(left), mergeSort(right)); //BreakPoint
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int n = 0, i = 0, j = 0;
        while (i < left.length || j < right.length) {
            if (i >= left.length)
                result[n++] = right[j++];
            else if (j >= right.length)
                result[n++] = left[i++];
            else {
                if (left[i] <= right[j])
                    result[n++] = left[i++];
                else
                    result[n++] = right[j++];
            }
        }
        return result; //BreakPoint
    }

    /**
     * 快速排序
     * 两头指针内移
     *
     * 7 5 2 4 3 pivot=7
     * 3 5 2 4|7 pivot=3
     * 2 3|5 4|7 pivot=5
     * 2 3|4 5|7
     */
    public static int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 对arr[left,right]区间进行左右划分（双向双指针）
     * @param arr
     * @param left  子序列首
     * @param right 子序列尾
     * @return
     */
    public static int[] quickSort(int[] arr, int left, int right) {
        int L = left, R = right; //左右指针
        if (L >= R) return arr;
        int pivot = arr[L];
        while (L < R) {
            // 每次都有L<R, 是为了避免指针移动时移过头
            // 找到比基准值更小的
            while (L < R && arr[R] >= pivot) R--;
            // 放到L,此时R空出
            if (L < R) arr[L] = arr[R];
            //找出比基准值更大的
            while (L < R && arr[L] < pivot) L++;
            // 放到R, 此时L空出
            if (L < R) arr[R] = arr[L];
        }
        arr[L] = pivot;
        quickSort(arr, left, L - 1);
        quickSort(arr, L + 1, right);
        return arr;
    }

    /**
     * 找出支点 （快排另一种写法的子函数，单向双指针）
     */
    private int partition(int[] nums, int left, int right)  {
        int pivot = left;
        int index =pivot+1;
        for (int i = index; i <=right; i++) {
            if(nums[i] < nums[pivot]){
                swap(nums, index, i);
                index++;
            }
        }
        swap(nums, pivot, index-1);
        return index-1;
    }

    /**
     * 堆排序 HeapSort（以最大堆为例，升序）(优先队列)
     *
     * 5 7 2 4 3
     * 7 5 2 4 3
     * 5 4 2 3|7
     * 4 3 2|5 7
     * 3 2|4 5 7
     * 2|3 4 5 7
     */
    public static int[] heapSort(int[] arr) {
        // 初始化最大堆
        buildMaxHeap(arr, arr.length);
        for (int i = arr.length - 1; i >= 0; i--) {
            // 最大堆的根节点与最后一个交换，相当于移出堆（末尾为已排列好）
            swap(arr, 0, i);
            // 重排交换后的堆，此时堆大小已减少，大小等于i
            heapify(arr, 0, i);
        }
        return arr;
    }

    /**
     * 建最大堆，以数组（完全二叉树）表示堆
     */
    public static void buildMaxHeap(int[] arr, int len) {
        // 完全二叉树的后半为叶节点
        // 遍历父节点构建最大堆
        for (int i = arr.length / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    /**
     * 对父节点i和其左右子节点重组，i为父节点下标
     */
    public static void heapify(int[] arr, int i, int len) {
        // 节点i的子节点
        int left = 2 * i + 1, right = 2 * i + 2;
        //大节点
        int largest = i;
        //左子节点更大
        if (left < len && arr[left] > arr[largest]) largest = left;
        // 右子节点更大
        if (right < len && arr[right] > arr[largest]) largest = right;
        // 有更大节点
        if (largest != i) {
            swap(arr, i, largest);
            // 对原父节点的现子节点再次重排
            heapify(arr, largest, len);
        }
    }

    /**
     * 计数排序
     */
    public static int[] countingSort(int[] arr) {
        int max = arr[0], min = arr[0];
        for (int val : arr) {
            if (max < val) max = val;
            if (min > val) min = val;
        }
        int[] count = new int[max - min + 1];
        for (int val : arr) {
            count[val - min]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = min + i;
                count[i]--;
            }
        }
        return arr;
    }

    /**
     * 桶排序（使用二维数组，注意数组范围）
     */
    public static int[] bucketSort(int[] arr) {
        int BUCKET_SIZE = 5; //桶中数值范围大小，自定义
        // 得到最大最小值，划分范围
        int max = arr[0], min = arr[0];
        for (int val : arr) {
            if (max < val) max = val;
            if (min > val) min = val;
        }
        int bucketCount = (max - min) / BUCKET_SIZE + 1;
        // 初始化桶
        int[][] buckets = new int[bucketCount][0];

        //根据映射函数放入桶
        for (int val : arr) {
            int index = (val - min) / BUCKET_SIZE;
            // 添加数据到对应桶，注意如果是数组要小心范围
            buckets[index] = arrAppend(buckets[index],val);
        }
        int arrIndex = 0;
        for (int[] bucket : buckets) {
            //桶中没有数据
            if(bucket.length<=0) continue;
            // 对桶内数据排序
            quickSort(bucket);
            // 导出桶内数据
            for (int val : bucket) {
                arr[arrIndex++] = val;
            }
        }
        return arr;
    }



    /**
     * 基数排序
     */
    public static int[] radixSort(int[] arr){
        int maxDigit = getMaxDigit(arr);
        int dev = 1; //对数 n 求倒数第i位的数字：n/dev%10 (dev = 10^(i-1))
        for (int i = 0; i < maxDigit; i++,dev*=10) {
            int[][] buckets = new int[10][0];
            for (int val : arr) {
                int index = val / dev % 10;
                buckets[index] = arrAppend(buckets[index], val);
            }
            int arrIndex =0;
            for (int[] bucket : buckets) {
                System.out.println(Arrays.toString(bucket));
                for (int val : bucket) {
                    arr[arrIndex++] = val;
                }
            }
            System.out.println(Arrays.toString(arr));
            System.out.println("--------");
        }
        return arr;
    }

    /**
     * 获取数组中数值的最高位
     */
    public static int getMaxDigit(int[] arr){
        int max=arr[0];
        for (int val : arr) {
            if (max < val) max = val;
        }
        if(max==0) return 1;
        int numberLength=0;
        while(max!=0){
            max/=10;
            numberLength++;
        }
        return numberLength;
    }

    /**
     * 交换arr数组中下标为i，j的元素
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 添加元素进数组，并扩容
     */
    private static int[] arrAppend(int[] arr, int value){
        arr = Arrays.copyOf(arr, arr.length+1);
        arr[arr.length-1] = value;
        return arr;
    }
}
